Messaging systems allow a message recipient to listen to an audio message via his telephone or other audio terminal. In so-called voicemail systems, when the message is accessed from the voicemail system, the voicemail system typically presents header information, such as the time of receipt of the message and the identity of the sender, if known, and plays a recorded message, consisting of a segment of audio material, to the recipient. The recipient can navigate through the recorded message using his telephone keypad or voice input that can effect a skip, rewind, pause, or other similar operations. Recently, integrated messaging systems have been introduced that have voice interfaces that can handle conventional voicemail messages as well as messages of other media types, such as email. In the latter case, a textual email message is delivered to recipient's mailbox. When retrieved by the recipient through his audio terminal, the email header information is converted to audio and presented to the recipient together with the body of the message, which is played for the recipient using text-to-speech processing. Thus, in both the traditional voicemail systems and the integrated messaging systems, the body of the message is interpreted as a monolithic chunk of recorded audio or text, the latter being converted to audio, which audio in either case is played linearly to the recipient when he accesses his messaging system from his telephone or other audio terminal.